package open.interview;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;

import junit.framework.Assert;

public class ArrayMiddle {

	public static int[] getSort() {
		int[] a = new int[new Random().nextInt(5) + 1];
		for (int i = 0; i < a.length; i++) {
			a[i] = new Random().nextInt(100);
		}

		Arrays.sort(a);
		for (int i : a)
			System.out.print(i + " ");
		System.out.println();

		return a;
	}

	public static int[] median2(int[] a1, int[] a2) {
		List<Integer> list = new ArrayList<Integer>();
		for (int a : a1)
			list.add(a);
		for (int a : a2)
			list.add(a);

		Collections.sort(list);
		for (int a : list)
			System.out.print(a + " ");
		System.out.println(" | " + list.size());

		int[] ret = new int[2];
		ret[0] = -1;
		ret[1] = -1;
		if (list.size() % 2 == 0) {
			ret[0] = list.get(list.size() / 2 - 1);
		}
		ret[1] = list.get(list.size() / 2);

		return ret;
	}

	/* *********************************************
	 * 
	 * Find the median
	 * 
	 * ********************************************
	 */
	public static int[] median(int[] a1, int[] a2) {
		int[] ret = new int[2];
		ret[0] = -1;
		ret[1] = -1;

		int offset = (a1.length + a2.length) / 2;

		if ((a1.length + a2.length) % 2 == 0) {
			ret[0] = median(a1, a2, offset - 1);
		}

		ret[1] = median(a1, a2, offset);
		return ret;
	}

	public static int median(int[] a1, int[] a2, int offset) {
		int middle = median(a1, a2, 0, a2.length - 1, offset);
		if (middle == -1)
			middle = median(a2, a1, 0, a1.length - 1, offset);

		return middle;
	}

	public static int median(int[] a1, int[] a2, int b2, int e2, int offset) {
		if (b2 > e2)
			return -1;

		int middle = (b2 + e2) / 2;

		int left = offset - middle;

		if (left > 0 && left < a1.length) {
			if (a1[left - 1] > a2[middle]) {
				return median(a1, a2, middle + 1, e2, offset);
			} else if (a1[left] < a2[middle]) {
				return median(a1, a2, b2, middle - 1, offset);
			} else {
				return a2[middle];
			}
		}

		if (left <= 0) {
			if (left == 0 && a1[0] >= a2[middle])
				return a2[middle];
			else
				return median(a1, a2, b2, middle - 1, offset);
		} else {
			if (left == a1.length && a1[a1.length - 1] <= a2[middle])
				return a2[middle];
			else
				return median(a1, a2, middle + 1, e2, offset);
		}
	}

	public static void testMedian(int repeat) {
		for (int i = 0; i < repeat; i++) {
			testMedian();
		}
	}

	public static void testMedian() {
		int[] a1 = { 12, 43, 45, 58, 74 };
		int[] a2 = { 10, 15, 22, 41, 77, 81, 99 };

		a1 = getSort();
		a2 = getSort();
		int[] median2 = median2(a1, a2);
		int[] median = median(a1, a2);

		String s = median[0] + " " + median[1] + " " + median2[0] + " "
				+ median2[1];
		Assert.assertEquals(s, median[0], median2[0]);
		Assert.assertEquals(s, median[1], median2[1]);
	}

	/**
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		testMedian(100000);
	}
}
